package cn.javadog.algorithm.e1_100;


/**
 * 搜索插入位置
 * https://leetcode-cn.com/problems/search-insert-position/
 * @author Sprite
 */
public class Algorithm35 {
	public static void main(String[] args) {
	}

	public int searchInsert(int[] nums, int target) {
		if (nums.length == 0) return 0;

		int startIdx = 0;
		int endIdx = nums.length-1;
		while (endIdx-startIdx > 1){
			int checkIdx = (startIdx+endIdx)/2;
			if (nums[checkIdx] == target){
				return checkIdx;
			}else if (nums[checkIdx] > target){
				startIdx = checkIdx;
			}else {
				endIdx = checkIdx;
			}
		}

		if (nums[endIdx] < target){
			return endIdx + 1;
		}else if (nums[startIdx] < target){
			return startIdx + 1;
		}else {
			return startIdx;
		}

	}
}
